	// /* we replace e with the last element in the heap.  We might need to
		//    shift it upward if it is less than its parent, or downward if it is
		//    greater than one or both its children. Since the children are known
		//    to be less than the parent, it can't need to shift both up and
		//    down. */
#include "min_heap.h"
int min_heap_push(min_heap_t *s, struct event *e)
{
    if (min_heap_reserve(s, s->n + 1))
        return -1;
    min_heap_shift_up_(s, s->n++, e);
    return 0;
}
// 分配队列的大小 ， n代表队列元素个数的多少
int min_heap_reserve(min_heap_t *s, unsigned int n)
{
    if (s->a < n)
    {
        struct event **p;                 // 队列大小不足元素的个数
        unsigned a = s->a ? s->a * 2 : 8; // s->a不为0时数量x2 为0时初始化为8
        if (a < n)
            a = n; // 翻倍后空间依然不足就分配n
        if (!(p = (struct event **)realloc(s->p, a * sizeof(*p))))
            return -1;
        s->p = p;
        s->a = a;
    }
    return 0;
}

// 最小堆向上规整
// 本质是假设在hole_index处插入e，
// 然后将
void min_heap_shift_up_(min_heap_t *s, unsigned hole_index, struct event *e)
{
    unsigned parent = __get_parent(hole_index);
    // 在父节点大于子节点并且子节点没有到达根节点时循环
    while (hole_index && min_heap_elem_greater(s->p[parent], e))
    {
        struct event *tmp;
        // 进行交换父子结点
        s->p[hole_index] = s->p[parent];
        s->p[hole_index]->ev_timeout_pos.min_heap_idx = hole_index;
        hole_index = parent;
        parent = __get_parent(hole_index);
    }
    s->p[hole_index] = e;
    s->p[hole_index]->ev_timeout_pos.min_heap_idx = hole_index;
}

void min_heap_shift_down_(min_heap_t *s, unsigned int hole_index, struct event *e)
{
    // min_child 相当于右子节点
    unsigned min_child = 2 * (hole_index + 1);

    // 当前节点小于等于队列元素的数量
    while (min_child <= s->n)
    {
        // 找出较小的字节点
        // 如果是最后一个则减去1 如果是右节点比左结点大的话则减一 右节点比左结点小则-0
        min_child -= (min_child == s->n) || (min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]));
        // 比最小子节点小则退出循环
        if (!(min_heap_elem_greater(e, s->p[min_child])))
            break;
        // 比最小子节点大则需要交换位置
        s->p[hole_index] = s->p[min_child];
        s->p[hole_index]->ev_timeout_pos.min_heap_idx = hole_index;
        // 子节点转移到父节点
        hole_index = min_child;
        min_child = 2 * (hole_index + 1);
    }
    s->p[hole_index] = e;
    e->ev_timeout_pos.min_heap_idx = hole_index;
}

// 返回min_heap的容量
int min_heap_size(min_heap_t *s)
{
    return s->n;
}

// 对于最小堆的事件的key进行比较
int min_heap_elem_greater(struct event *a, struct event *b)
{

    return evutil_timercmp(&a->ev_timeout, &b->ev_timeout, >);
}
// 某个元素是否是时间堆的顶部
int min_heap_elt_is_top(const struct event *e)
{
	return e->ev_timeout_pos.min_heap_idx == 0;
}

// 删除时间堆中的某个元素
int min_heap_erase(min_heap_t* s, struct event* e)
{   
    // 确保这个元素在时间最小堆中 否则返回-1
	if (-1 != e->ev_timeout_pos.min_heap_idx)
	{   
        // 获取最小堆中最后一个元素
		struct event *last = s->p[--(s->n)];
        // 获取这个元素的父亲节点
		unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
        // 将这个元素e和最后一个元素互换
        // 如果这个元素e不是头结点 并且它的父亲节点比最后一个节点大的话
		if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
            // e->ev_timeout_pos.min_heap_idx 想要删除事件的在最小堆中的index
            // last在这个最小堆中的最后一个元素
            // 等同于将最小堆中的最后一个元素插入到先要删除的元素的位置再进行梳理
			min_heap_shift_up_(s, e->ev_timeout_pos.min_heap_idx, last);
		else
			min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last);
        // 将删除元素的index置为-1
		e->ev_timeout_pos.min_heap_idx = -1;
		return 0;
	}
	return -1;
}
